#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

import os


class Solution(object):
    def findAndReplacePattern(self, words, pattern):
        """
        :type words: List[str]
        :type pattern: str
        :rtype: List[str]
        """
        res = []
        for word in words:
            if self.match(word, pattern):
                res.append(word)
        
        return res

    def match(self, word, pattern):
        map1 = {}
        map2 = {}
        for i in range(len(word)):
            w = word[i]
            p = pattern[i]
            if map1.get(w, None) is None:
                map1[w] = p
            if map2.get(p, None) is None:
                map2[p] = w

            if map1[w] != p or map2[p] != w:
                return False

        return True


class Solution1(object):
    def findAndReplacePattern(self, words, pattern):
        """
        :type words: List[str]
        :type pattern: str
        :rtype: List[str]
        """
        res = []
        for word in words:
            if self.match(word, pattern):
                res.append(word)

        return res

    def match(self, word, pattern):
        posw = [-1 for _ in range(126)]
        posp = [-1 for _ in range(126)]
        
        for i in range(len(word)):
            w = word[i]
            p = pattern[i]
            if posw[ord(w)] != posp[ord(p)]:
                return False

            posw[ord(w)] = posp[ord(p)] = i

        return True


